package a09_贪心算法;

//比如下一步最多能跳到第3个格子
//然后计算下一步的下一步最多能跳到第6个格子
public class a08_跳跃游戏2复习1 {

    public static void main(String[] args) {
        int jump = jump(new int[]{2,1,1,1,1});
        System.out.println(jump);
    }

    public static int jump(int[] nums) {
        int result = 0;

        int cover = 0;//当前覆盖范围
        int nextCover = Integer.MIN_VALUE;//下一个最大的覆盖范围，目前不知道
        int currentIdx = 0;
        while (currentIdx <= cover) {
            //计算下一个最大的覆盖范围
            nextCover = Math.max(nextCover, currentIdx + nums[currentIdx]);

            if(currentIdx == cover){//到达当前范围的边界了(感觉只有第一次循环才有可能走到这里)
                if(currentIdx == nums.length - 1){//已经到数组最后了，直接返回
                    return result;
                }else {//没有到数组最后，继续
                    cover = nextCover;
                    result++;
                    currentIdx++;
                    nextCover = Integer.MIN_VALUE;
                    if(cover >= nums.length - 1){
                        return result;
                    }
                }
            }else {//没有到达当前范围的边界了
                currentIdx++;
            }
        }
        return result;
    }
}
